﻿// AI导论-4.1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <chrono>
#include <iostream>
#include<algorithm>
using namespace std;
#include<vector>
#include<utility>
#include<string>
#include<queue>
vector<pair<int,int>> tree[30];
vector<pair<int,int>>record1;
struct ComparePairSecond {
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second >rhs.second; // 按照 pair 的 second 元素从小到大排序
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, ComparePairSecond>pq;
priority_queue<pair<int, int>, vector<pair<int, int>>, ComparePairSecond>USQ;
int greedy(int map[100][100], pair<string, int> distance[100], int pass, int depth,int length=0)
{
    pair<int, int> record = make_pair(0x3f3f, 0x3f3f);
    if (pass == 1)
    {
        cout << "长度为" << length << endl;
        cout << "深度为" << depth << endl;
        return  depth;
    }
    else
    {
        vector<int> way;
        for (int i = 0; i < 20; i++)
        {
            if (map[pass][i] != 1000)
            {
                way.push_back(i);
            };
        };
        for (auto it : way)
        {
            if (distance[it].second < record.second)
            {
                record.first = it;
                record.second = distance[it].second;
            }
        };
        depth+=1;
        cout << "经过";
        cout << distance[record.first].first << endl;
        length += map[pass][record.first];
        greedy(map,distance, record.first, depth,length);

    };
};
void AF(int map[100][100], pair<string, int> distance[100], int i = 0)
{
    if (pq.top().first == 1)
    {
       cout << "finish" << endl;
        cout << "distance" << pq.top().second;
        cout << "经过节点数" << i;
        return;
    }
    i++;
    pair<int, int>parents = pq.top();
    cout << "经过" << distance[pq.top().first].first<< endl;
    pq.pop();
    for (int i = 0; i < 20; i++)
    {
        if (map[parents.first][i] != 1000 && map[parents.first][i] != 0)
        {
            tree[i].push_back(parents);
            int a = map[parents.first][i] + (parents.second -distance[parents.first].second)+distance[i].second;
            pq.push(make_pair(i, a));
            cout << "插入元素" << distance[i].first << "值" << a << endl;
        };
    };
    AF(map, distance,i);

}
void UCS(int map[100][100], pair<string, int> distance[100],int last = 1)
{
    int i = 0;
    int site[20];
    for (int i = 0; i < 20; i++)
    {
        site[i] = 0;
    }
    while (USQ.top().first != last)
    {
       
        i++;
        pair<int, int> making = USQ.top();
        
        USQ.pop();
        site[making.first] = 1;
        for (int i = 0; i < 20; i++)
        {
            if (map[making.first][i] != 1000 && map[making.first][i] != 0&&site[i]!=1)
            {
                int a = making.second + map[making.first][i];
                USQ.push(make_pair(i, a));
                cout << "扫描至" << distance[i].first<<"代价为"<<a << endl;
                site[i] = 1;
            }
        }
    };
    cout << "循环完毕" << USQ.top().second << endl;
    cout << "节点拓张为" << i;
    return;
}
int main()
{
    int map[100][100];
    static pair<string, int> distance[100];
    distance[0] = make_pair("Arad", 366);
    distance[1] = make_pair("Bucharest", 0);
    distance[2] = make_pair("Craiova", 160);
    distance[3] = make_pair("Doberta", 242);
    distance[4] = make_pair("Eforie", 161);
    distance[5] = make_pair("Fagaras", 176);
    distance[6] = make_pair("Glurgiu", 77);
    distance[7] = make_pair("Hirsova", 151);
    distance[8] = make_pair("Iasi", 226);
    distance[9] = make_pair("Lugoj", 244);
    distance[10] = make_pair("Mehadia", 241);
    distance[11] = make_pair("Neamt", 234);
    distance[12] = make_pair("Oradea", 380);
    distance[13] = make_pair("Pitesti", 10);
    distance[14] = make_pair("Rimmicu_Vikea", 193);
    distance[15] = make_pair("Sibiu", 253);
    distance[16] = make_pair("Timisoara", 329);
    distance[17] = make_pair("Urziceni", 80);
    distance[18] = make_pair("Vaslui", 199);
    distance[19] = make_pair("Zerind", 374);
    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j< 20; j++)
        {
            cin >> map[i][j];
        };
    };
    vector<int> show[20];
    for (int i = 0; i <20; i++)
    {
        cout << distance[i].first << " " << "->";
        for (int j = 0; j < 20; j++)
        {
           
            if (map[i][j] != 1000 &&map[i][j] != 0)
            {
               
                cout << distance[j].first << " ";
            };
            
        };
        cout << endl;
    };
    cout << "请输入想要运行的方式" << endl;
    cout << "1 A*算法" << endl;
    cout << "2 贪心算法" << endl;
    cout << "3 代价一致的宽度优先搜索算法" << endl;
    int tag;
    cin >> tag;
    if (tag == 1)
    {
        auto start = chrono::high_resolution_clock::now();
        pq.push(make_pair(0, 366));
        AF(map, distance);
        auto end = std::chrono::high_resolution_clock::now();
        chrono::duration<double> duration = end - start;
        cout << "函数执行时长: " << duration.count() << " 秒" << std::endl;
    };
    if (tag == 2)
    {
        auto start = chrono::high_resolution_clock::now();
        int depth = greedy(map, distance, 0, 0);
        auto end = std::chrono::high_resolution_clock::now();
        chrono::duration<double> duration = end - start;
        cout << "函数执行时长: " << duration.count() << " 秒" << std::endl;
    }
    if (tag == 3)
    {
        auto start = chrono::high_resolution_clock::now();
        USQ.push(make_pair(0, 0));
        UCS(map,distance);
        auto end = std::chrono::high_resolution_clock::now();
        chrono::duration<double> duration = end - start;
        cout << "函数执行时长: " << duration.count() << " 秒" << std::endl;
    }

    
   /* pair<int, int>min = make_pair(1, 0x3f3f);
    for (int i = 0; i < 20; i++)
    {
        for (auto it : tree[i])
        {
            cout <<"内容" << distance[it.first].first << endl;
        }
    }
    for (auto it : tree[1])
    {
        if (it.second < min.second)
        {
        
            min.second = it.second;
            min.first = it.first;
        };
    };*/
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
